package com.ding.practice.algorithm.leetcode.hot100;

import java.util.*;

/**
 * 力扣热题100之三数和
 * @ID = 15
 * @date 2024年07月17日11:03:26
 * 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
 *
 * 你返回所有和为 0 且不重复的三元组。
 *
 * 注意：答案中不可以包含重复的三元组。
 *
 * 示例 1：
 *
 * 输入：nums = [-1,0,1,2,-1,-4]
 * 输出：[[-1,-1,2],[-1,0,1]]
 * 解释：
 * nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
 * nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
 * nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
 * 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
 * 注意，输出的顺序和三元组的顺序并不重要。
 * 示例 2：
 *
 * 输入：nums = [0,1,1]
 * 输出：[]
 * 解释：唯一可能的三元组和不为 0 。
 * 示例 3：
 *
 * 输入：nums = [0,0,0]
 * 输出：[[0,0,0]]
 * 解释：唯一可能的三元组和为 0 。
 *
 *
 * 提示：
 *
 * 3 <= nums.length <= 3000
 * -105 <= nums[i] <= 105
 */
public class ThreeSum_15 {
    /*
    此题解法为先对数组进行排序，方便找到连续相等的数字，然后抽离出来一个当做固定值，采用首尾双指针进行遍历，与固定值进行相加和为0即可
    关键点：
    1、在首尾双指针遍历的过程中，应跳过重复的值，防止有重复解出现
    2、移动左指针还是右指针取决于当前值大于0还是小于0，大于0说明需要负值，则移动大的一边，即右指针，让和小一点。反之亦然
     */
    public static List<List<Integer>> threeSum(int[] nums){
        List<List<Integer>> retList= new ArrayList<>();
        Arrays.sort(nums);
        int index = 0;
        while (index < nums.length){
            // 如果最小的数都大于0,那肯定不存在和为0的数了，直接返回
            if (nums[index] > 0){
                break;
            }
            // 去重，当当前遍历的数和之前的相同，则跳出本次循环
            if (index > 0 && nums[index] == nums[index - 1]){
                index ++;
                continue;
            }
            int lp = index + 1;
            int rp = nums.length - 1;
            while (lp < rp){
                int sum = nums[index] + nums[lp] + nums[rp];
                if (sum == 0){
                    // 如果等于0，说明找的这三个值就是想要的
                    List<Integer> tempList = new ArrayList<>();
                    tempList.add(nums[index]);
                    tempList.add(nums[lp]);
                    tempList.add(nums[rp]);
                    retList.add(tempList);
                    while(lp < rp && nums[lp] == nums[lp+1]) {
                        lp++;
                    }
                    // 为何要同时移动两个左右指针，找到两个数值和之前不一样的？
                    // 因为有一个值nums【index】已经固定，并且当前左右指针和index的值刚好为0，如果只移动一个指针，那肯定合不为0，除非两个值一样，所以两个指针要一起移动
                    //去重，因为 i不变，当此时 r 取的数的值与前一个相同，所以不用在计算
                    while(lp< rp && nums[rp] == nums[rp-1]){
                        rp--;
                    }
                    //将 左指针右移，将右指针左移。
                    lp++;
                    rp--;
                }else if (sum < 0){
                    // 如果合小于0，则需要更大的值，故把左指针小的值右移
                    lp ++;
                } else if (sum > 0){
                    rp --;
                }
            }
           index ++;

        }


        return retList;
    }

    public static void main(String[] args) {
        int[] nums = {-1,0,1,2,-1,-4};
        System.out.println(threeSum(nums));
    }
}
